package j2025.j01;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @Author 猫大仙
 */
public class j0126 {

    /**
     * 32. 最长有效括号
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号
     * 子串
     * 的长度。
     * @param s
     * @return
     */
    public int longestValidParentheses(String s) {
        int n = s.length();
        int[] dp = new int[n];
        int max = 0;
        for (int i = 1; i < n; i++) {
            if(s.charAt(i) == ')'){
                //判断前一个字符是')'还是'('
                //如果是'(',则更新结果,dp[i] = dp[i-2]+2
                //如果是')',找到匹配的'('的位置,跳过dp[i-1],dp[i] = dp[i-dp[i-1]-2]+dp[i-1]+2
                if(s.charAt(i-1) == '('){
                    dp[i] = (i-2>=0?dp[i-2]:0)+2;
                }else if(i-dp[i-1]-1>=0 && s.charAt(i-dp[i-1]-1) == '('){
                    dp[i] = dp[i-1] + dp[((i-dp[i-1]-2)>=0?(i-dp[i-1]-2):0)] + 2;
                }
                max = Math.max(max,dp[i]);
            }
        }
        return max;
    }


    public int longestValidParentheses2(String s) {
        //始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」
        int n = s.length();
        Deque<Integer> stack = new LinkedList<>();
        int max = 0;
        stack.push(-1);
        for (int i = 0; i < n; i++) {
            if(s.charAt(i) == '('){
                stack.push(i);
            }else {
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else {
                    max = Math.max(max,i-stack.peek());
                }
            }
        }
        return max;
    }
    public int longestValidParentheses3(String s) {
        //计数器方法

        int left = 0,right = 0,max = 0;
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '('){
                left++;
            }else {
                right++;
            }
            if(left ==  right){
                max = Math.max(max,left+right);
            }else if(right>left){
                left  = right = 0;
            }
        }
        for (int i = s.length()-1; i >= 0; i--) {
            if(s.charAt(i) == '('){
                left++;
            }else {
                right++;
            }
            if(left == right){
                max = Math.max(max,left+right);
            }else if(left>right){
                left  = right = 0;
            }
        }
        return max;
    }
}
